/*
 * exame_2009_10_julho_Q3.c
 *
 *  Created on: Jun 19, 2012
 *      Author: ubuntu
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "exame_2009_10_junho_types.h"
#include "7JUL2010_q3.c"

#include "exame_2009_10_junho_btreeAPI.c"

void inorder(ArvBin a) {
	if (a == NULL)
		return;
	inorder(a->esq);
	printf("%d ", a->valor);
	inorder(a->dir);
}

void preorder(ArvBin a) {
	if (a == NULL)
		return;
	printf("%d ", a->valor);
	preorder(a->esq);
	preorder(a->dir);
}

void postorder(ArvBin a) {
	if (a == NULL)
		return;
	postorder(a->esq);
	postorder(a->dir);
	printf("%d ", a->valor);
}

////////////

void preorderIT(ArvBin a) {

	if (a == NULL) {
		return;
	}

	int bunchAllocAmount = 3;
	int stackMemorySize = bunchAllocAmount;
	ArvBin * stack = (ArvBin *) malloc(sizeof(ArvBin) * stackMemorySize);
	int stackSize = 0;

	ArvBin node = a;

	while (node != NULL) {
		printf("%d ", node->valor);
		if (node->esq != NULL) {
			// push
			if (node->dir != NULL) {
				if (stackMemorySize == stackSize) {
					stack = (ArvBin *) realloc(stack,
							sizeof(ArvBin)
									* (stackMemorySize + bunchAllocAmount));
					stackMemorySize += bunchAllocAmount;
				}

				stack[stackSize] = node->dir;
				stackSize++;
			}
			node = node->esq;
			continue;
		}
		if (node->esq != NULL) {
			node = node->esq;

			continue;
		}

		// pop
		if (stackSize > 0) {
			node = stack[stackSize - 1];
			stack[stackSize - 1] = NULL;
			stackSize--;
		} else {
			node = NULL;
		}

	}
}

ArvBin fillArvBin(int level, int valor) {
	if (level == 0) {
		return NULL;
	}

	ArvBin arvBin = (ArvBin) malloc(sizeof(NodoArvBin));

	int valorAux = 0;

	arvBin->esq = fillArvBin(level - 1, valor);
	if (arvBin->esq == NULL) {
		valorAux = valor;
	} else if (arvBin->esq->dir != NULL) {
		valorAux = arvBin->esq->dir->valor + 1;
	} else {
		valorAux = arvBin->esq->valor + 1;
	}
	arvBin->valor = valorAux;
	arvBin->dir = fillArvBin(level - 1, valorAux + 1);

	return arvBin;
}

int main(int argc, char **argv) {
	if (argc < 2) {
		fprintf(stderr, "Usage %s <arvSize>\n", argv[0]);
		exit(EXIT_FAILURE);
	}

	int arvSize = atoi(argv[1]);

	ArvBin arvBinRoot = fillArvBin(arvSize, 1);

	puts("\n===================================");
	puts("preorder");
	preorder(arvBinRoot);

	puts("\n===================================");
	puts("preorder ITERATIVE");
	preorderIT(arvBinRoot);

	puts("\n===================================");
	puts("preorder ITERATIVE G");
	preorderItG(arvBinRoot);

	puts("\n===================================");
	puts("postorder");
	postorder(arvBinRoot);

	puts("\n===================================");
	puts("inorder");
	inorder(arvBinRoot);
	puts("");

	puts("Testes");
	// criar arvore com 3 nodes, e 7 elemetos de 1 a 7
	ArvBin arvBinRootTeste = fillArvBin(3, 1);

	if (contaNodos(arvBinRootTeste) == 7) {
		puts("Pre-condition verification OK");
	}
	if (existe(arvBinRootTeste, 1) == 1 && existe(arvBinRootTeste, -1) == 0) {
		puts("existe base tests OK");
	} else {
		puts("existe FAIL");
	}

	if (adicionar(arvBinRootTeste, 8) != NULL
			&& contaNodos(arvBinRootTeste) == 8) {
		puts("adicionar base tests OK");
	} else {
		puts("adicionar FAIL");
	}
	return 0;
}
